Digital halftoning is a technique employing digital image processing to produce halftone output image from a continuous-tone image. In the digital halftoning technique, a continuous-tone image is sampled, for example, with a scanner and the samples are digitized and stored in a computer. The digitized samples (or "pixels") consist of discrete values typically ranging from 0 to 255. To reproduce this image on an output device capable of printing dots of one gray level (e.g. black), it is necessary to convert the continuous-tone image to a binary output image using some form of halftoning techniques. Halftoning methods rely on the fact that an observer's eye will spatially average over some local area of the image so that intermediate gray levels can be created by turning some of the pixels "on" and some of the pixels "off" in some small region. The fraction of the pixels that are turned on will determine the apparent gray level. Common prior art methods of digital halftoning include error diffusion and dithering.
Error diffusion is an adaptive algorithm that produces patterns with different spatial frequency content depending on the input image value. FIG. 1 shows a block diagram describing a basic error diffusion technique disclosed in "An adaptive algorithm for spatial greyscale," Proceedings of the Society for Information Display, vol. 17, no. 2, pp. 75-77, 1976, by R. W. Floyd and L. Steinberg. For purpose of illustration it will be assumed that the continuous-tone input values span the range from 0 to 255. The continuous-tone input value for the current input pixel is thresholded 10 to form the output value. The threshold operator will return a 0 for any continuous-tone input value below the threshold, and a 255 for any continuous-tone input value above the threshold. A difference signal generator 12 receives the continuous-tone input value and the output value, and produces a difference signal representing the error introduced by the thresholding process. The difference signal is multiplied by a series of error feedback weights using a weighted error generator 14, and is provided to an adder 16 which adds the weighted difference signal to the continuous-tone input values of the nearby pixels that have yet to be processed to form modified continuous-tone input values. The propagation of the errors made during the thresholding process to the nearby pixels insures that the arithmetic mean of the pixel values is preserved over a local image region.
FIG. 2 illustrates a typical set of error feedback weights 14 which can be used to distribute the errors to the nearby pixels. The halftone output from error diffusion is considered to be of high quality generally, since most of the halftone noise is distributed in a high spatial frequency band where human visual sensitivity is relatively low. An artifact that is typically associated with error diffusion halftoning technique is known as "worms." Worms are formed when the black or white output pixels appear to string together in an area that should be otherwise uniform. Worm artifacts can be clearly seen in several areas of the output gray wedge (c) in FIG. 4 from the error diffusion halftoning technique, such as the light and dark ends of the gray wedge (c). Several of these worm artifacts are labelled as 40A-C.
Compared to the error diffusion technique, halftoning with a dithering technique is simpler in implementation, which is shown in FIG. 3. In this case, a periodic dither signal d(x', y') is determined by modularly addressing 30, 32 a dithering matrix 34 with the row and column addresses of the input pixels. The size of the dither matrix in this example is M.sub.x by M.sub.y. The periodic dither signal is then provided to an adder 36 which adds the periodic dither signal to the input pixel value I(x,y) to form modified continuous-tone input values. The modified continuous-tone input pixel is then thresholded 38 to form the output value. The threshold operator will return a 0 for any modified continuous-tone input value below the threshold, and a 255 for any modified continuous-tone input value above the threshold. The modulo operations 30, 32 have the effect of tiling the dither matrix 34 across the image in a repeating pattern. Obviously, the arrangement of the values stored in the dither matrix will determine the output halftone patterns. Commonly used dither matrices are the clustered-dot dither matrices and the "Bayer matrix". However, due to the ordered structure imposed by these two matrices (thus called "ordered dithering"), the resulting halftone output normally contains distinct textures that are highly visible. Recent developments in the dithering technique have been concentrated on "blue-noise dithering" (for example see "Design of minimum visual modulation halftone patterns," IEEE Trans. Syst. Man. Cybern. SMC-21(1), pp. 33-38, 1991, by J. R. Sullivan, et al.; "Digital halftoning technique using a blue-noise mask," Journal of Optical Society of America A 9(11), pp. 1920-1929, 1992, by K. J. Parker, et al.; "Methods for generating blue-noise dither matrices for digital halftoning," Journal of Electronic Imaging, vol. 6, pp. 208-230, April 1997, by K. E. Spaulding, et al.; and, "Stochastic screen halftoning for electronic devices," Journal of Visual Communication and Image Representation, vol. 8, pp. 423-440, December 1997, by Q. Yu and K. J. Parker), where blue-noise dither matrices are designed that minimize the low frequency content and maximize the high frequency content in the halftone patterns, thus producing similar results as error diffusion halftone patterns. The blue-noise dither matrices are typically relatively large in size, and can be seamlessly tiled to cover the image due to the built-in wrap-around properties. The major artifact associated with blue-noise dithering is increased graininess at mid-tone gray levels, relative to that associated with error diffusion. The graininess artifact can be seen in the gray wedge (b) in FIG. 4, which is labelled as 42.
Recently, printing devices with multilevel output (N output levels, where N&gt;2) capability have been brought to the market to achieve photographic image quality. Both dithering and error diffusion techniques can be generalized for these devices, in which case halftoning becomes multitoning. For multilevel dithering, the process is equivalent to the binary implementation in FIG. 3, except that the threshold operation 38 is replaced by a quantization operation. As before, the periodic dither signal is added to the input pixel value. The quantizer then associates one of the allowable output levels with each of the possible values of the modulated input pixel value. Similarly, for multilevel error diffusion, the process is equivalent to the binary implementation in FIG. 1 except that the thresholding 10 step is replaced with a quantization step.
FIG. 4 shows a continuous-tone gray wedge (a) along with outputs from binary blue-noise dithering (b), binary error diffusion (c), multilevel blue- noise dithering (d) and multilevel error diffusion (e). In the multitoning cases (d and e), the total number of output levels (N) is 4. It can be observed that overall image quality is improved while texture visibility is reduced from blue-noise dithering to error diffusion as well as from halftoning to multitoning. Also, the typical artifacts 40A-C, 42 associated with both error diffusion and blue-noise dithering are clearly visible.
It can be seen from FIG. 4 that both the multilevel error diffusion and multilevel dithering halftoning algorithm produce distinct contours near the 4 pure printing states (or "boundaries", or output gray levels). Additionally both of these two approaches result in distinct texture transitions near the 2 intermediate output levels. These can be called "texture contours", which are labelled as 44 in the two output wedges (d) and (e) in FIG. 4.
The texture contouring problem could be explained with the following analysis. For input image values right at the output levels, since there is no halftone (or multitone) error introduced, there is no visual noise. However, if the input value is a few code values away from those output levels, the output halftone pattern is rendered with sparse minority pixels over a uniform majority- pixel background. Since human visual system is very sensitive to these kinds of dot patterns, the perceived "grain" is much higher. Therefore, if an input continuous-tone input image contains a smooth transition across a certain boundary, then with the conventional multitoning approaches, there will be a distinct texture change in the output image which is observed as texture contouring within certain viewing distances.
"Digital multitoning evaluation with a human visual model," Proceedings of NIP 13: International Conference on Digital Printing Technologies, (Seattle, Wash.), IS&T, November 1997, by Q. Yu, et al discloses an approach to smooth the texture transition at the N output levels for multilevel blue-noise dithering with precisely controlled over-modulated dither patterns. A brief description is given here in below.
FIG. 5 shows the flow chart of the over-modulation method where a dither matrix guided modulation operation is added before the conventional multilevel dithering. For each input pixel value I(x,y) that is within a predetermined neighbourhood of a certain output level X, a modulation processor 50 is called, which requires as inputs the input pixel value I(x,y), the value of the specific output level X and a periodic dither signal S which is determined by modularly addressing 30, 32 a dither matrix with the row and column addresses of I(x,y). The modified input pixel value I'(x,y) is then used as the input for the conventional multitoning processor 52 to get the final output image value O(x,y). This over-modulation process is non-linear, and could be best described with the following pseudo computer code (assuming that the input pixel values range from 0 to 255):
D = I - X; A = MAP(D); if (D &gt;= 0) if (S &gt;= 128) I' = X - A; else I' = I + A; else if (S &gt;= 128) I' = I - A; else I' = X + A;
where MAP is a pre-set mapping function (a simple one 60 is shown in FIG. 6) that controls the degree of over-modulation such that the resulting output multilevel image will contain more than two output levels for those input pixel values near the N output levels.
Special blue-noise dither matrices have been designed, and along with the MAP function, they can precisely control the texture of the over- modulated patterns near the N output levels. It was found that the over-modulated patterns resulting from a "binar" dither matrix were preferred by human observers over those from other dither matrices. The "binar" dither matrix is so named since its large dither matrix elements are paired and are arranged to be adjacent to its small dither matrix elements. An example of the over-modulation patterns from a "binar" dither matrix is shown in FIG. 7, where pixels of lower output level 70 and pixels of higher output level 71 are introduced in pairs to an uniform input image whose pixel values are equal to one specific output level 72.
"An improved multilevel error diffusion method," Journal of Imaging Science and Technology, vol. 39, no. 6, pp. 495-501, 1995, by S. Sugiura, et al. discloses adding noise using a 4 by 4 ordered dither matrix for a wide range of input pixel values around the N output levels, thus eliminating the texture contouring at the N output levels for multilevel error diffusion. However, this is at the expense of increased halftone visibility over a wide range of the tonescale and the interaction between ordered dither matrix and error diffusion could result in artifacts due to the lack of precise control of halftone patterns around the N output levels.